public class LeetCode5 {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1){
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            // 处理奇数长度回文（单中心）
            int[] odd = extend(s, i, i);
            // 处理偶数长度回文（双中心）
            int[] even = extend(s, i, i + 1);
            // 比较并更新最长回文
            int[] longer = (odd[1] - odd[0] > even[1] - even[0]) ? odd : even;
            if (longer[1] - longer[0] > end - start) {
                start = longer[0];
                end = longer[1];
            }
        }
        return s.substring(start, end + 1);
    }

    public int[] extend(String str, int left, int right) {
        while (left >= 0 && right < str.length()
                && str.charAt(left) == str.charAt(right)) {//如果是回文，扩大范围
            left--;
            right++;
        }
        //不是回文
        return new int[]{left + 1, right - 1};
    }
}
